package msb.class02;


import org.junit.Assert;
import org.junit.Test;
import common.pojo.LinkedNode;
import common.util.ArrayUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 单向链表中删除指定数
 */
public class Code03_DeleteValueInSinglyLinked {


    public static LinkedNode delete(LinkedNode head, int value) {
        while (head != null && head.value == value) {
            head = head.next;
        }

        LinkedNode pre = head;
        LinkedNode current = head.next;
        while (current != null) {
            if (current.value == value) {
                pre.next = null;
            } else {
                pre.next = current;
                pre = current;
            }
            current = current.next;
        }
        return head;
    }


    public List<LinkedNode> instance() {
        List<LinkedNode> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            LinkedNode node = new LinkedNode();
            node.value = ArrayUtil.randomInt(1, 50);
            list.add(node);
        }
        for (int i = 0; i < 99; i++) {
            list.get(i).next = list.get(i + 1);
        }
        return list;
    }

    @Test
    public void test() {
        for (int n = 0; n < 10000; n++) {
            List<LinkedNode> list = instance();
            int target = ArrayUtil.randomInt(1, 50);
            LinkedNode head = delete(list.get(0), target);
            for (int i = list.size() - 1; i >= 0; i--) {
                if (list.get(i).value == target) {
                    list.remove(i);
                }
            }
            LinkedNode current = head;
            for (int i = 0; i < list.size(); i++) {
                Assert.assertEquals(list.get(i).value, current.value);
                current = current.next;
            }
        }
    }
}

